package gold.digger;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC808 {
    public long startExecuteTime = System.currentTimeMillis();

    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 动归骚操作
     * 未来需要再次复习此道题目
     * @return:
     */
    class Solution {
        public double soupServings(int N) {
            N = N / 25 + (N % 25 > 0 ? 1 : 0);
            if (N >= 500) return 1.0;

            double[][] memo = new double[N + 1][N + 1];
            for (int s = 0; s <= 2 * N; ++s) {
                for (int i = 0; i <= N; ++i) {
                    int j = s - i;
                    if (j < 0 || j > N) continue;
                    double ans = 0.0;
                    if (i == 0) ans = 1.0;
                    if (i == 0 && j == 0) ans = 0.5;
                    if (i > 0 && j > 0) {
                        ans = 0.25 * (memo[M(i - 4)][j] + memo[M(i - 3)][M(j - 1)] +
                                memo[M(i - 2)][M(j - 2)] + memo[M(i - 1)][M(j - 3)]);
                    }
                    memo[i][j] = ans;

                }
            }
            return memo[N][N];
        }

        public int M(int x) {
            return Math.max(0, x);
        }
    }


    public void run() {
        Solution solution = new Solution();
        List<Integer> list = new ArrayList<>();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC808 an = new LC808();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
